{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check if String Is Decomposable Into Value-Equal Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isDecomposable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断字符串是否可分解为值均等的子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个字符串的所有字符都是一样的，被称作等值字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举例，<code>\"1111\"</code> 和 <code>\"33\" </code>就是等值字符串。</li>\n",
    "\t<li>相比之下，<code>\"123\"</code>就不是等值字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>规则：给出一个数字字符串s，将字符串分解成一些等值字符串，如果有且仅有一个等值子字符串长度为2，其他的等值子字符串的长度都是3.</p>\n",
    "\n",
    "<p>如果能够按照上面的规则分解字符串s，就返回真，否则返回假。</p>\n",
    "\n",
    "<p>子串就是原字符串中连续的字符序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> s = \"000111000\"\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释: </strong> s只能被分解长度为3的等值子字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> s = \"00011111222\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释: </strong>s 能被分解为 [\"000\",\"111\",\"11\",\"222\"].\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> s = \"01110002223300\"\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释: </strong>一个不能被分解的原因是在开头有一个0.\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;</code><code>= 1000</code></li>\n",
    "\t<li><code>s</code> 仅包含数字。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-string-is-decomposable-into-value-equal-substrings](https://leetcode.cn/problems/check-if-string-is-decomposable-into-value-equal-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-string-is-decomposable-into-value-equal-substrings](https://leetcode.cn/problems/check-if-string-is-decomposable-into-value-equal-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"000111000\"', '\"00011111222\"', '\"011100022233\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        arr = []\n",
    "        n = len(s)\n",
    "        pre = s[0]\n",
    "        count = 1\n",
    "        for i in range(1, n):\n",
    "            if s[i] == pre:\n",
    "                count += 1\n",
    "                if i == n - 1:\n",
    "                    arr.append(count % 3)\n",
    "            else:\n",
    "                arr.append(count % 3)\n",
    "                count = 1\n",
    "                pre = s[i]\n",
    "                if i == n - 1:\n",
    "                    arr.append(count % 3)\n",
    "        count = 0\n",
    "        for num in arr:\n",
    "            if num == 2:\n",
    "                count += 1\n",
    "            elif num == 0:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return count == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        a = []\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n and s[j] == s[i]:\n",
    "                j += 1\n",
    "            a.append((j - i)%3)\n",
    "            i = j\n",
    "        a = [x for x in a if x != 0]\n",
    "        return len(a) == 1 and a[0] == 2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n < 5 and n != 2:\n",
    "            return False\n",
    "        \n",
    "        next, cnt2, compare = 1, 0, s[0]\n",
    "        while next < n:\n",
    "            cnt = 1\n",
    "            while next < n and s[next] == compare:\n",
    "                next += 1\n",
    "                cnt += 1\n",
    "                if cnt > 3:\n",
    "                    cnt = 1\n",
    "                    \n",
    "            if cnt % 3 and cnt % 2 :\n",
    "                return False\n",
    "                \n",
    "            if cnt == 2:\n",
    "                 cnt2 += 1\n",
    "                 \n",
    "            if cnt2 > 1:\n",
    "                return False\n",
    "                \n",
    "            if next < n:\n",
    "                compare = s[next]\n",
    "                cnt = 1\n",
    "                next += 1\n",
    "                \n",
    "        return True if cnt2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        temp = []\n",
    "        pre = s[0]\n",
    "        count = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != pre:\n",
    "                temp.append(count)\n",
    "                pre = s[i]\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "        temp.append(count)\n",
    "        # print(temp)\n",
    "        count_2 = 0\n",
    "        for num in temp:\n",
    "            if num % 3 == 0:\n",
    "                continue\n",
    "            elif num % 3 == 2:\n",
    "                count_2 += 1\n",
    "            else:\n",
    "                return False\n",
    "        return count_2 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        two = 0\n",
    "        l = 1\n",
    "        s = s + 'x'\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i-1]:\n",
    "                l += 1\n",
    "            else:\n",
    "                #print(l)\n",
    "                if l % 3 == 1:\n",
    "                    return False\n",
    "                if l % 3 == 2:\n",
    "                    if two:\n",
    "                        return False\n",
    "                    two = 1\n",
    "                l = 1\n",
    "        return two == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "      i = 0\n",
    "      two = 0\n",
    "      while i<len(s):\n",
    "        j = i+1\n",
    "        while j< len(s) and s[i] ==s[j]:\n",
    "          j+=1\n",
    "        if(j-i)%3 == 1:\n",
    "          return False\n",
    "        if(j-i)%3 == 2:\n",
    "          two+=1\n",
    "        i = j     \n",
    "      return two ==1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n < 5 and n != 2:\n",
    "            return False\n",
    "        \n",
    "        next, cnt2, compare = 1, 0, s[0]\n",
    "        while next < n:\n",
    "            cnt = 1\n",
    "            while next < n and s[next] == compare:\n",
    "                next += 1\n",
    "                cnt += 1\n",
    "                if cnt > 3:\n",
    "                    cnt = 1\n",
    "                    \n",
    "            if cnt % 3 and cnt % 2 :\n",
    "                return False\n",
    "                \n",
    "            if cnt == 2:\n",
    "                 cnt2 += 1\n",
    "                 \n",
    "            if cnt2 > 1:\n",
    "                return False\n",
    "                \n",
    "            if next < n:\n",
    "                compare = s[next]\n",
    "                cnt = 1\n",
    "                next += 1\n",
    "                \n",
    "        return True if cnt2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isDecomposable(self, s: str) -> bool:\r\n",
    "        len_2 = False\r\n",
    "        n = len(s)\r\n",
    "        i = 0\r\n",
    "        while i < n:\r\n",
    "            cur_len = 1\r\n",
    "            while i + 1 < n and s[i] == s[i+1]:\r\n",
    "                i += 1\r\n",
    "                cur_len += 1\r\n",
    "            if cur_len % 3 == 2:      #当前这段长度模3为2。分成5 = 2 + 3\r\n",
    "                if len_2 == True:       #长度为2的段只能有一个\r\n",
    "                    return False\r\n",
    "                len_2 = True\r\n",
    "            else:           \r\n",
    "                if cur_len % 3 != 0:\r\n",
    "                    return False\r\n",
    "            i += 1      #指向下一段的第一个位置\r\n",
    "        \r\n",
    "        return len_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n < 5 and n != 2:\n",
    "            return False\n",
    "        \n",
    "        next, cnt2, compare = 1, 0, s[0]\n",
    "        while next < n:\n",
    "            cnt = 1\n",
    "            while next < n and s[next] == compare:\n",
    "                next += 1\n",
    "                cnt += 1\n",
    "                if cnt > 3:\n",
    "                    cnt = 1\n",
    "                    \n",
    "            if cnt % 3 and cnt % 2 :\n",
    "                return False\n",
    "                \n",
    "            if cnt == 2:\n",
    "                 cnt2 += 1\n",
    "                 \n",
    "            if cnt2 > 1:\n",
    "                return False\n",
    "                \n",
    "            if next < n:\n",
    "                compare = s[next]\n",
    "                cnt = 1\n",
    "                next += 1\n",
    "                \n",
    "        return True if cnt2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isDecomposable(self, s: str) -> bool:\n",
    "#         slow=0\n",
    "#         fast=0\n",
    "#         res=[]\n",
    "#         n=len(s)\n",
    "#         if len(s)==1:\n",
    "#             return False\n",
    "#         if s[0]!=s[1]:\n",
    "#             return False\n",
    "#         while fast<n:\n",
    "#             while s[slow]==s[fast]:\n",
    "#                 fast+=1\n",
    "#                 if fast==n:\n",
    "#                     break\n",
    "#             # 当快慢指针不相同，相减就是当前子串长度\n",
    "#             s1=fast-slow\n",
    "#             # 子串长度对 3 求余，最后检查列表里是不是 1 个 2，其余都是 0，因为题意是 1 个 2，其他都是 3。\n",
    "#             m=s1%3\n",
    "#             res.append(m)\n",
    "#             # 把慢指针放到快指针位置上，找下一个子串。\n",
    "#             slow=fast\n",
    "#         # 最后生成的 res，符合题意的话，只有 1 个 2，其他都是 0，所以总和是 2，但需要避免 2 个 1 的情况。\n",
    "#         # count(1) 统计列表中 1 的数量\n",
    "#         if sum(res)==2 and res.count(1)==0:\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        res=[]\n",
    "        slow,fast=0,0\n",
    "        while fast<n:\n",
    "            while s[slow]==s[fast]:\n",
    "                fast+=1\n",
    "                # n-1的时候+1 就是 n 了\n",
    "                if fast==n:\n",
    "                    break\n",
    "            diff=fast-slow\n",
    "            m=diff%3\n",
    "            res.append(m)\n",
    "            slow=fast\n",
    "        print(res)\n",
    "        if sum(res)==2 and res.count(1)==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n < 5 and n != 2:\n",
    "            return False\n",
    "        \n",
    "        next, cnt2, compare = 1, 0, s[0]\n",
    "        while next < n:\n",
    "            cnt = 1\n",
    "            while next < n and s[next] == compare:\n",
    "                next += 1\n",
    "                cnt += 1\n",
    "                if cnt > 3:\n",
    "                    cnt = 1\n",
    "                    \n",
    "            if cnt % 3 and cnt % 2 :\n",
    "               # print(cnt)\n",
    "                return False\n",
    "            if cnt == 2:\n",
    "                 cnt2 += 1\n",
    "            if cnt2 > 1:\n",
    "               # print(cnt2)\n",
    "                return False\n",
    "                \n",
    "            if next < n:\n",
    "                compare = s[next]\n",
    "                cnt = 1\n",
    "                next += 1\n",
    "        print(cnt2)\n",
    "        return True if cnt2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        num=1\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            if i==n-1 or s[i]!=s[i+1]:\n",
    "                if num%3==1:\n",
    "                    return False\n",
    "                elif num%3==2:\n",
    "                    cnt+=1\n",
    "                    if cnt>1:\n",
    "                        return False \n",
    "                num=1\n",
    "            else:\n",
    "                num+=1\n",
    "        return cnt==1#True\n",
    "                 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isDecomposable(self, s: str) -> bool:\n",
    "        cnt2 = 0\n",
    "        for _, g in groupby(s):\n",
    "            m = len(list(g))\n",
    "            if m % 3 == 1:\n",
    "                return False\n",
    "            cnt2 += m % 3 == 2\n",
    "            if cnt2 > 1:\n",
    "                return False\n",
    "        return cnt2 == 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
